/* 
 * Copyright (C) 2013, 2014 lex xiang
 *
 * file:	sys/rbtree.c
 * history:	2013 Juy 25 created by lex
 *
 * rule of red black tree
 * 1. A node is either red or black.
 * 2. The root is black. 
 * 3. All leaves (NIL) are black. (All leaves are same color as the root.)
 * 4. Both children of every red node are black.
 * 5. Every simple path from a given node to any of its descendant leaves 
 *    contains the same number of black nodes.
 */

#include "rbtree.h"

static void rb_rotate_left(struct rb_tree *tree, struct rb_node *node)
{
	struct rb_node *root   = tree->root;
	struct rb_node *right  = node->right_child;
	struct rb_node *parent = node->parent;

	if ((node->right_child = right->left_child))
		right->left_child->parent = node;
	right->left_child = node;

	right->parent = parent;

	if (parent) {
		if (node == parent->left_child)
			parent->left_child = right;
		else
			parent->right_child = right;
	}
	else {
		root = right;
	}

	node->parent = right;

	return;
}

static void rb_rotate_right(struct rb_tree *tree, struct rb_node *node)
{
	struct rb_node *root   = tree->root;
	struct rb_node *left   = node->left_child;
	struct rb_node *parent = node->parent;

	if ((node->left_child = left->right_child))
		left->right_child->parent = node;
	left->right_child = node;

	left->parent = parent;

	if (parent) {
		if (node == parent->right_child)
			parent->right_child = left;
		else
			parent->left_child = left;
	}
	else {
		root = left;
	}

	node->parent = left;

	return;
}

struct rb_node *rb_first(struct rb_tree *tree)
{
	struct rb_node *node = tree->root;

	if (!node)
		return NULL;

	while (node->left_child)
		node = node->left_child;

	return node;
}

struct rb_node *rb_last(struct rb_tree *tree)
{
	struct rb_node *node = tree->root;

	if (!node)
		return NULL;

	while (node->right_child)
		node = node->right_child;

	return node;
}

struct rb_node *rb_next(struct rb_node *node)
{
	struct rb_node *parent;

	if ((parent = node->parent) == node)
		return NULL;

	if (node->right_child) {
		node = node->right_child;
		while (node->left_child)
			node = node->left_child;
		return node;
	}

	while ((parent = node->parent) && node == parent->right_child)
		node = parent;

	return parent;
}

struct rb_node *rb_prev(struct rb_node *node)
{
	struct rb_node *parent;

	if (node->parent == node)
		return NULL;

	if (node->left_child) {
		node = node->left_child;
		while (node->right_child)
			node = node->right_child;

		return node;
	}

	while ((parent = node->parent) && node == parent->left_child)
		node = parent;

	return parent;
}

static void rb_insert_color(struct rb_tree *tree, struct rb_node *node)
{
	struct rb_node *parent, *gparent;

	while ((parent = node->parent) && (parent->color == RB_RED)) {
		gparent = parent->parent;

		if (parent == gparent->left_child) {
			register struct rb_node *uncle = gparent->right_child;

			if (uncle && uncle->color == RB_RED) {
				uncle->color   = RB_BLACK;
				parent->color  = RB_BLACK;
				gparent->color = RB_RED;

				node = gparent;
				continue;
			}

			if (parent->right_child == node) {
				register struct rb_node *tmp;

				rb_rotate_left(tree, parent);
				tmp    = parent;
				parent = node;
				node   = tmp;
			}

			parent->color  = RB_BLACK;
			gparent->color = RB_RED;
			rb_rotate_right(tree, gparent);

		} 
		else {
			register struct rb_node *uncle = gparent->left_child;

			if (uncle && uncle->color == RB_RED) {
				uncle->color   = RB_BLACK;
				parent->color  = RB_BLACK;
				gparent->color = RB_RED;
				node           = gparent;
				continue;
			}

			if (parent->left_child == node) {
				register struct rb_node *tmp;

				rb_rotate_right(tree, parent);
				tmp    = parent;
				parent = node;
				node   = tmp;
			}

			parent->color  = RB_BLACK;
			gparent->color = RB_RED;
			rb_rotate_left(tree, gparent);
		}
	}

	tree->root->color = RB_BLACK;

	return;
}

void rb_tree_init(struct rb_tree *tree, 
		  fp_rbtree_find rb_find, fp_rbtree_insert rb_insert, 
		  fp_rbtree_erase rb_erase, fp_rbtree_cmp rb_cmp)
{
	tree->root	= NULL;
	tree->first	= NULL;

	tree->op.find	= rb_find;
	tree->op.insert	= rb_insert;
	tree->op.erase	= rb_erase;
	tree->op.cmp	= rb_cmp;

	return;
}

#include "uart.h"
struct rb_node **rb_find(struct rb_tree *tree, struct rb_node *parent, void *key)
{
	s32 value;
	struct rb_node **p;

	if (!tree->op.cmp)
		return NULL;

	p = &tree->root;

	while (*p) {
		parent = *p;

		value = tree->op.cmp(parent, key);
		if (value > 0)
			p   = &(*p)->left_child;
		else if (value < 0)
			p   = &(*p)->right_child;
		else
			break;
	}

	return p;
}

void rb_insert(struct rb_tree *tree, struct rb_node *node, 
	       struct rb_node *parent, struct rb_node **p)
{
	node->parent = parent;
	node->left_child = node->right_child = NULL;
	*p = node;

	if (tree->root == NULL) {
		tree->root = node;
		tree->root->color = RB_BLACK;
		tree->first = node;
	}
	else {
		rb_insert_color(tree, node);
		tree->first = rb_first(tree);
	}
	
	return;
}

void rb_erase(struct rb_tree *tree, struct rb_node *node)
{
	return;
}

